package leetcode.code;

import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.*;

/**
 * @author : zx
 * @version V1.0
 */
public class 简单题 {

    /**
     * 写字符串需要的行数
     *
     * 我们要把给定的字符串 S 从左到右写到每一行上，每一行的最大宽度为100个单位，如果我们在写某个字母的时候会使这行超过了100 个单位，那么我们应该把这个字母写到下一行。我们给定了一个数组 widths ，这个数组 widths[0] 代表 'a' 需要的单位， widths[1] 代表 'b' 需要的单位，...， widths[25] 代表 'z' 需要的单位。
     *
     * 现在回答两个问题：至少多少行能放下S，以及最后一行使用的宽度是多少个单位？将你的答案作为长度为2的整数列表返回。
     *
     * 示例 1:
     * 输入:
     * widths = [10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]
     * S = "abcdefghijklmnopqrstuvwxyz"
     * 输出: [3, 60]
     * 解释:
     * 所有的字符拥有相同的占用单位10。所以书写所有的26个字母，
     * 我们需要2个整行和占用60个单位的一行。
     * 示例 2:
     * 输入:
     * widths = [4,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]
     * S = "bbbcccdddaaa"
     * 输出: [2, 4]
     * 解释:
     * 除去字母'a'所有的字符都是相同的单位10，并且字符串 "bbbcccdddaa" 将会覆盖 9 * 10 + 2 * 4 = 98 个单位.
     * 最后一个字母 'a' 将会被写到第二行，因为第一行只剩下2个单位了。
     * 所以，这个答案是2行，第二行有4个单位宽度。
     *  
     *
     * 注:
     *
     * 字符串 S 的长度在 [1, 1000] 的范围。
     * S 只包含小写字母。
     * widths 是长度为 26的数组。
     * widths[i] 值的范围在 [2, 10]。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/number-of-lines-to-write-string
     *
     */
    public int[] numberOfLines(int[] widths, String S) {
        int maxWidth = 100;
        int row = 0;
        int[] res = new int[]{1,0};
        for(int i = 0; i < S.length(); i++){
            int tmp = widths[S.charAt(i)-'a'];
            row += tmp;
            if(row > maxWidth){
                row = tmp;
                res[0]++;
            }
        }
        res[1] = row;
        return res;
    }

    /**
     * 给定一个正整数，返回它在 Excel 表中相对应的列名称。
     *
     * 例如，
     *
     *     1 -> A
     *     2 -> B
     *     3 -> C
     *     ...
     *     26 -> Z
     *     27 -> AA
     *     28 -> AB
     *     ...
     * 示例 1:
     *
     * 输入: 1
     * 输出: "A"
     * 示例 2:
     *
     * 输入: 28
     * 输出: "AB"
     * 示例 3:
     *
     * 输入: 701
     * 输出: "ZY"
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/excel-sheet-column-title
     */
    public static String convertToTitle(int n) {
        StringBuilder sb = new StringBuilder();
        while (n > 0) {
            int c = n % 26;
            if(c == 0){
                c = 26;
                n -= 26; // 低位用A表出 则原值-26
            }
            sb.insert(0, (char) ('A' + c - 1));
            n /= 26;
        }
        return sb.toString();
    }

    /**
     * 给出第一个词 first 和第二个词 second，考虑在某些文本 text 中可能以 "first second third" 形式出现的情况，其中 second 紧随 first 出现，third 紧随 second 出现。
     *
     * 对于每种这样的情况，将第三个词 "third" 添加到答案中，并返回答案。
     *
     *  
     *
     * 示例 1：
     *
     * 输入：text = "alice is a good girl she is a good student", first = "a", second = "good"
     * 输出：["girl","student"]
     * 示例 2：
     *
     * 输入：text = "we will we will rock you", first = "we", second = "will"
     * 输出：["we","rock"]
     *  
     *
     * 提示：
     *
     * 1 <= text.length <= 1000
     * text 由一些用空格分隔的单词组成，每个单词都由小写英文字母组成
     * 1 <= first.length, second.length <= 10
     * first 和 second 由小写英文字母组成
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/occurrences-after-bigram
     *
     * @param text
     * @param first
     * @param second
     * @return
     */
    public String[] findOcurrences(String text, String first, String second) {
        String[] list = text.split(" ");
        List<String> a = new ArrayList<>();
        for (int i = 0; i < list.length; i++){
            if(list[i].equals(first)){
                i++;
                if(i < list.length && list[i].equals(second)){
                    i++;
                    if(i < list.length){
                        a.add(list[i]);
                        i++;
                    }
                }else{
                    i--;
                }
            }
        }
        String[] b = new String[a.size()];
        b = a.toArray(b);
        return b;
    }

    public int isPrefixOfWord(String sentence, String searchWord) {
        String[] sens = sentence.split(" ");
        int len = searchWord.length();
        int j = 1;
        for(String s : sens){
            for(int i = 0; i < len && i < s.length(); i++){
                if(searchWord.charAt(i) == s.charAt(i)){
                    if(i == len-1){
                        return j;
                    }
                }else{
                    break;
                }
            }
            j++;
        }
        return -1;
    }

    /**
     *  统计最大组的数目
     *
     * 给你一个整数 n 。请你先求出从 1 到 n 的每个整数 10 进制表示下的数位和（每一位上的数字相加），然后把数位和相等的数字放到同一个组中。
     *
     * 请你统计每个组中的数字数目，并返回数字数目并列最多的组有多少个。
     *
     *  
     *
     * 示例 1：
     *
     * 输入：n = 13
     * 输出：4
     * 解释：总共有 9 个组，将 1 到 13 按数位求和后这些组分别是：
     * [1,10]，[2,11]，[3,12]，[4,13]，[5]，[6]，[7]，[8]，[9]。总共有 4 个组拥有的数字并列最多。
     * 示例 2：
     *
     * 输入：n = 2
     * 输出：2
     * 解释：总共有 2 个大小为 1 的组 [1]，[2]。
     * 示例 3：
     *
     * 输入：n = 15
     * 输出：6
     * 示例 4：
     *
     * 输入：n = 24
     * 输出：5
     *  
     *
     * 提示：
     *
     * 1 <= n <= 10^4
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/count-largest-group
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */
    public int countLargestGroup(int n) {
        HashMap<Integer, Integer> m = new HashMap<>();
        for (int i = 1; i <= n; i++){
            int tmp = i;
            int sum = 0;
            sum += tmp % 10;
            while ((tmp /= 10) != 0){
                sum += tmp % 10;
            }
            if (m.containsKey(sum)){
                m.put(sum, m.get(sum)+1);
            }else {
                m.put(sum, 1);
            }
        }
        int maxLength = Integer.MIN_VALUE;
        int nums = 0;
        for (Map.Entry<Integer, Integer> i : m.entrySet()){
            if (maxLength < i.getValue()){
                maxLength = i.getValue();
                nums = 1;
            }else if (maxLength == i.getValue()) {
                nums++;
            }
        }
        return nums;
    }


    /**
     * 快乐数
     *
     * 编写一个算法来判断一个数 n 是不是快乐数。
     *
     * 「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为  1，那么这个数就是快乐数。
     *
     * 如果 n 是快乐数就返回 True ；不是，则返回 False 。
     *
     *  
     *
     * 示例：
     *
     * 输入：19
     * 输出：true
     * 解释：
     * 12 + 92 = 82
     * 82 + 22 = 68
     * 62 + 82 = 100
     * 12 + 02 + 02 = 1
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/happy-number
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */
    public static boolean isHappy(int n) {

        int slow = squart(n);
        int quick = squart(slow);
        while (slow != quick){
            slow = squart(slow);
            quick = squart(squart(quick));
        }
        return (squart(slow) == 1);
    }

    private static int squart(int n){
        int a = n%10;
        int tmp = a*a;
        while ((n /= 10) != 0){
            a = n%10;
            tmp += a*a;
        }
        return tmp;
    }

    public int distributeCandies(int[] candies) {
        int n = candies.length;
        HashSet<Integer> m = new HashSet<>();
        for (int i : candies){
            m.add(i);
        }
        if (m.size() > n/2){
            return n/2;
        }else {
            return m.size();
        }
    }

    // 旋转数组的最小数字
    public int minArray(int[] numbers) {
            int i = 0, j = numbers.length - 1;
            while (i < j) {
                int m = (i + j) / 2;
                if (numbers[m] > numbers[j]) i = m + 1;
                else if (numbers[m] < numbers[j]) j = m;
                else j--;
            }
            return numbers[i];
    }

    /**
     *
     * 假设 力扣（LeetCode）即将开始其 IPO。为了以更高的价格将股票卖给风险投资公司，力扣 希望在 IPO 之前开展一些项目以增加其资本。 由于资源有限，它只能在 IPO 之前完成最多 k 个不同的项目。帮助 力扣 设计完成最多 k 个不同项目后得到最大总资本的方式。
     *
     * 给定若干个项目。对于每个项目 i，它都有一个纯利润 Pi，并且需要最小的资本 Ci 来启动相应的项目。最初，你有 W 资本。当你完成一个项目时，你将获得纯利润，且利润将被添加到你的总资本中。
     *
     * 总而言之，从给定项目中选择最多 k 个不同项目的列表，以最大化最终资本，并输出最终可获得的最多资本。
     *
     * 示例 1:
     *
     * 输入: k=2, W=0, Profits=[1,2,3], Capital=[0,1,1].
     *
     * 输出: 4
     *
     * 解释:
     * 由于你的初始资本为 0，你尽可以从 0 号项目开始。
     * 在完成后，你将获得 1 的利润，你的总资本将变为 1。
     * 此时你可以选择开始 1 号或 2 号项目。
     * 由于你最多可以选择两个项目，所以你需要完成 2 号项目以获得最大的资本。
     * 因此，输出最后最大化的资本，为 0 + 1 + 3 = 4。
     *  
     *
     * 注意:
     *
     * 假设所有输入数字都是非负整数。
     * 表示利润和资本的数组的长度不超过 50000。
     * 答案保证在 32 位有符号整数范围内。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/ipo
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */
    public int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
        int max = W;
        List<int[]> p = new LinkedList<>();
        for (int i = 0; i < Profits.length; i++){
            p.add(new int[]{Profits[i], Capital[i]});
        }
        p.sort(((o1, o2) -> o2[0]-o1[0]));
        while (!p.isEmpty() && k>0){
            for (int i = 0; i < p.size(); i++){
                int[] tmp = p.get(i);
                if (W >= tmp[1]){
                    k--;
                    W = W + tmp[0];
                    max += tmp[0];
                    p.remove(i);
                    break;
                }
                if (i == p.size()-1){
                    return max;
                }
            }
        }
        return max;
    }

    /**
     * 给定两个由小写字母构成的字符串 A 和 B ，只要我们可以通过交换 A 中的两个字母得到与 B 相等的结果，就返回 true ；否则返回 false 。
     * https://leetcode-cn.com/problems/buddy-strings/
     */
    public boolean buddyStrings(String A, String B) {
        if(A.length() != B.length() || A.length() < 2 ) return false;
        int len = A.length();
        boolean[] flag = new boolean[len];
        int[] letters = new int[26];
        int diff = 0;
        for(int i = 0; i < len; i++){
            if(A.charAt(i) != B.charAt(i)){
                flag[i] = true;
                diff++;
            }
            if(diff > 2) return false;
            letters[A.charAt(i)-'a']++;
        }
        if(diff == 0){
            for(int i : letters){
                if(i >= 2) return true;
            }
        }else if(diff == 2){
            int pos1=0,pos2=0;
            for(int i = 0; i < len; i++){
                if(flag[i]) {pos1 = i; break;}
            }
            for(int i = pos1+1; i < len; i++){
                if(flag[i]) {pos2 = i; break;}
            }
            if(A.charAt(pos1)==B.charAt(pos2) && A.charAt(pos2)==B.charAt(pos1)) return true;
        }
        return false;
    }

    // 阶乘后的零
    /**
     * 例如，如果 n=16n=16，我们需要查看 11 到 1616 之间所有数字的因子。我们只对 22 和 55 有兴趣。
     * 包含 55 因子的数字是 {5，10，15}5，10，15，包含因子 22 的数字是 {2、4、6、8、10、12、14、16}2、4、6、8、10、12、14、16。
     * 因为只三个完整的对，因此 16!16! 后有三个零。
     *
     * 又因为2 远多于 5 所以只计算5因子出现的次数
     *
     * 作者：LeetCode
     * 链接：https://leetcode-cn.com/problems/factorial-trailing-zeroes/solution/jie-cheng-hou-de-ling-by-leetcode/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    public int trailingZeroes(int n) {

        int zeroCount = 0;
        while (n > 0) {
            n /= 5;
            zeroCount += n;
        }
        return zeroCount;
    }

    /**
     * 8 间牢房排成一排，每间牢房不是有人住就是空着。
     *
     * 每天，无论牢房是被占用或空置，都会根据以下规则进行更改：
     *
     * 如果一间牢房的两个相邻的房间都被占用或都是空的，那么该牢房就会被占用。
     * 否则，它就会被空置。
     * （请注意，由于监狱中的牢房排成一行，所以行中的第一个和最后一个房间无法有两个相邻的房间。）
     *
     * 我们用以下方式描述监狱的当前状态：如果第 i 间牢房被占用，则 cell[i]==1，否则 cell[i]==0。
     *
     * 根据监狱的初始状态，在 N 天后返回监狱的状况（和上述 N 种变化）。
     *
     *  
     *
     * 示例 1：
     *
     * 输入：cells = [0,1,0,1,1,0,0,1], N = 7
     * 输出：[0,0,1,1,0,0,0,0]
     * 解释：
     * 下表概述了监狱每天的状况：
     * Day 0: [0, 1, 0, 1, 1, 0, 0, 1]
     * Day 1: [0, 1, 1, 0, 0, 0, 0, 0]
     * Day 2: [0, 0, 0, 0, 1, 1, 1, 0]
     * Day 3: [0, 1, 1, 0, 0, 1, 0, 0]
     * Day 4: [0, 0, 0, 0, 0, 1, 0, 0]
     * Day 5: [0, 1, 1, 1, 0, 1, 0, 0]
     * Day 6: [0, 0, 1, 0, 1, 1, 0, 0]
     * Day 7: [0, 0, 1, 1, 0, 0, 0, 0]
     *
     * 示例 2：
     *
     * 输入：cells = [1,0,0,1,0,0,1,0], N = 1000000000
     * 输出：[0,0,1,1,1,1,1,0]
     *  
     *
     * 提示：
     *
     * cells.length == 8
     * cells[i] 的值为 0 或 1 
     * 1 <= N <= 10^9
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/prison-cells-after-n-days
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */
    public int[] prisonAfterNDays(int[] cells, int N) {
        Map<String, Integer> map = new HashMap<>();
        while (N > 0) {
            int[] cells2 = new int[8];
            map.put(Arrays.toString(cells), N);
            N --;
            for (int i = 1; i < 7; i ++) {
                cells2[i] = cells[i - 1] == cells[i + 1] ? 1 : 0;
            }
            cells = cells2;
            if (map.containsKey(Arrays.toString(cells))) {
                N = N % (map.get(Arrays.toString(cells)) - N);
            }
        }
        return cells;
    }

    /**
     *
     * 给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法，将 B 合并入 A 并排序。
     *
     * 初始化 A 和 B 的元素数量分别为 m 和 n。
     *
     * 示例:
     *
     * 输入:
     * A = [1,2,3,0,0,0], m = 3
     * B = [2,5,6],       n = 3
     *
     * 输出: [1,2,2,3,5,6]
     * 说明:
     *
     * A.length == n + m
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/sorted-merge-lcci
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */
    public void merge(int[] A, int m, int[] B, int n) {
        int [] tmp = Arrays.copyOfRange(A, 0, m);
        int i = 0, j = 0;
        for (int k = 0; k < A.length; k++){
            if (i == tmp.length){
                A[k] = B[j];
                j++;
                continue;
            }
            if (j == B.length){
                A[k] = tmp[i];
                i++;
                continue;
            }
            if(tmp[i] < B[j]){
                A[k] = tmp[i];
                i++;
            }else {
                A[k] = B[j];
                j++;
            }
        }
    }

    /**
     *
     * 有 N 个花园，按从 1 到 N 标记。在每个花园中，你打算种下四种花之一。
     *
     * paths[i] = [x, y] 描述了花园 x 到花园 y 的双向路径。
     *
     * 另外，没有花园有 3 条以上的路径可以进入或者离开。
     *
     * 你需要为每个花园选择一种花，使得通过路径相连的任何两个花园中的花的种类互不相同。
     *
     * 以数组形式返回选择的方案作为答案 answer，其中 answer[i] 为在第 (i+1) 个花园中种植的花的种类。花的种类用  1, 2, 3, 4 表示。保证存在答案。
     *
     *  
     *
     * 示例 1：
     *
     * 输入：N = 3, paths = [[1,2],[2,3],[3,1]]
     * 输出：[1,2,3]
     * 示例 2：
     *
     * 输入：N = 4, paths = [[1,2],[3,4]]
     * 输出：[1,2,1,2]
     * 示例 3：
     *
     * 输入：N = 4, paths = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]]
     * 输出：[1,2,3,4]
     *  
     *
     * 提示：
     *
     * 1 <= N <= 10000
     * 0 <= paths.size <= 20000
     * 不存在花园有 4 条或者更多路径可以进入或离开。
     * 保证存在答案。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/flower-planting-with-no-adjacent
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */
    public static int[] gardenNoAdj(int N, int[][] paths) {

        int[][] allPaths = new int[paths.length*2][2];
        for (int i = 0; i < paths.length; i++){
            allPaths[i] = paths[i];
            allPaths[i+paths.length][0] = paths[i][1];
            allPaths[i+paths.length][1] = paths[i][0];
        }
        Arrays.sort(allPaths, ((o1, o2) -> o1[0]-o2[0]));
        int[] colors = new int[N+1];
        for (int i = 0; i < allPaths.length; i++){
            if (colors[allPaths[i][0]] != 0) continue;
            boolean[] tmp = new boolean[5];
            int curr = allPaths[i][0];
            while (i < allPaths.length && curr == allPaths[i][0]){
                tmp[colors[allPaths[i][1]]] = true;
                i++;
            }
            if (i < allPaths.length && curr != allPaths[i][0]) i--;
            for (int j = 1; j < tmp.length; j++){
                if (!tmp[j]) {colors[curr] = j; break;}
            }
        }
        for (int i = 0; i < colors.length; i++){
            if (colors[1] == 0) colors[i] = 1;
        }
        return Arrays.copyOfRange(colors, 1, colors.length);
    }

    /**
     *
     * 在 N * N 的网格上，我们放置一些 1 * 1 * 1  的立方体。
     *
     * 每个值 v = grid[i][j] 表示 v 个正方体叠放在对应单元格 (i, j) 上。
     *
     * 请你返回最终形体的表面积。
     *
     *  
     *
     * 示例 1：
     *
     * 输入：[[2]]
     * 输出：10
     * 示例 2：
     *
     * 输入：[[1,2],[3,4]]
     * 输出：34
     * 示例 3：
     *
     * 输入：[[1,0],[0,2]]
     * 输出：16
     * 示例 4：
     *
     * 输入：[[1,1,1],[1,0,1],[1,1,1]]
     * 输出：32
     * 示例 5：
     *
     * 输入：[[2,2,2],[2,1,2],[2,2,2]]
     * 输出：46
     *  
     *
     * 提示：
     *
     * 1 <= N <= 50
     * 0 <= grid[i][j] <= 50
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/surface-area-of-3d-shapes
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */
    public int surfaceArea(int[][] grid) {
        int area = 0;
        int m = grid.length, n = grid[0].length;
        int[] directions = new int[]{-1, 0, 1, 0, -1};
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                // top & bottom
                if(grid[i][j] > 0) area += 2;
                for(int z = 0; z < 4; z++){
                    int x = i+directions[z];
                    int y = j+directions[z+1];
                    if(x >= 0 && x < m && y >= 0 && y < n){
                        area += grid[i][j] - grid[x][y] > 0 ? grid[i][j] - grid[x][y] : 0;
                    }else{
                        area += grid[i][j];
                    }
                }
            }
        }
        return area;
    }

    public static class TreeNode {
        public int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    class Solution_1 {
        public int minDiffInBST(TreeNode root) {
            dfs(root);
            Integer[] a = new Integer[m.size()];
            a = m.toArray(a);
            Arrays.sort(a);
            int min = Integer.MAX_VALUE;
            for (int i = 1; i < a.length; i++){
                if (a[i]-a[i-1] < min){
                    min = a[i]-a[i-1];
                }
            }
            return min;
        }

        HashSet<Integer> m = new HashSet<>();
        public void dfs(TreeNode node){
            if(node != null){
                m.add(node.val);
                dfs(node.left);
                dfs(node.right);
            }
        }
    }

    /**
     * K次操作转变字符串
     *
     * 给你两个字符串 s 和 t ，你的目标是在 k 次操作以内把字符串 s 转变成 t 。
     *
     * 在第 i 次操作时（1 <= i <= k），你可以选择进行如下操作：
     *
     * 选择字符串 s 中满足 1 <= j <= s.length 且之前未被选过的任意下标 j （下标从 1 开始），并将此位置的字符切换 i 次。
     * 不进行任何操作。
     * 切换 1 次字符的意思是用字母表中该字母的下一个字母替换它（字母表环状接起来，所以 'z' 切换后会变成 'a'）。
     *
     * 请记住任意一个下标 j 最多只能被操作 1 次。
     *
     * 如果在不超过 k 次操作内可以把字符串 s 转变成 t ，那么请你返回 true ，否则请你返回 false 。
     *
     *  
     *
     * 示例 1：
     *
     * 输入：s = "input", t = "ouput", k = 9
     * 输出：true
     * 解释：第 6 次操作时，我们将 'i' 切换 6 次得到 'o' 。第 7 次操作时，我们将 'n' 切换 7 次得到 'u' 。
     * 示例 2：
     *
     * 输入：s = "abc", t = "bcd", k = 10
     * 输出：false
     * 解释：我们需要将每个字符切换 1 次才能得到 t 。我们可以在第 1 次操作时将 'a' 切换成 'b' ，但另外 2 个字母在剩余操作中无法再转变为 t 中对应字母。
     * 示例 3：
     *
     * 输入：s = "aab", t = "bbb", k = 27
     * 输出：true
     * 解释：第 1 次操作时，我们将第一个 'a' 切换 1 次得到 'b' 。在第 27 次操作时，我们将第二个字母 'a' 切换 27 次得到 'b' 。
     *  
     *
     * 提示：
     *
     * 1 <= s.length, t.length <= 10^5
     * 0 <= k <= 10^9
     * s 和 t 只包含小写英文字母。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/can-convert-string-in-k-moves
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */

    public static boolean canConvertString(String s, String t, int k) {
        int len1 = s.length();
        int len2 = t.length();

        if (len1 != len2){
            return false;
        }

        int[] arr = new int[26];

        //首先统计每个数字出现个数
        for (int i = 0; i < len1; i++){
            int times = ((t.charAt(i) - s.charAt(i) + 26) % 26);
            arr[times]++;
        }

        //数字出现多次，需要按照26的大小进行增大，并与k进行比较
        for (int i = 1; i < 26; i++){
            if ((arr[i] - 1) * 26 + i > k){
                return false;
            }
        }

        return true;
    }

    //
    public static void main(String[] args){

//        System.out.println(Arrays.toString(gardenNoAdj(4, new int[][]{{1,2},{3,4}})));
        System.out.println(canConvertString("input", "ouput", 9));
    }
}
